package com.interview.javabase.algorithm;

/**
 * @author: zsg
 * @description:
 * @date: 2019/8/23 21:31
 * @modified:
 */
public class CalculatorStack {

    public static void main(String[] args) {
        String expression = "3*3*21-2*12-3";

        ArrayStack1 valueStack = new ArrayStack1(50);
        ArrayStack1 operationStack = new ArrayStack1(50);

        int index = 0;

        int value1 = 0;
        int value2 = 0;
        int result = 0;
        int oper = 0;
        char ch = ' ';
        String concat = "";
        while (true) {
            ch = expression.substring(index, index + 1).charAt(0);
            System.out.println(ch);

            // 如果是符号
            if (isOperation(ch)) {
                if (operationStack.isEmpty()) {
                    operationStack.push(ch);
                } else {
                    // 如果是符号则比较优先级 如果优先级大则直接入栈 否则pop数栈前两个计算 结果在入栈
                    while (operationStack.priority(ch) <= operationStack.priority(operationStack.peek())) {
                        // pop进行计算
                        value1 = valueStack.pop();
                        value2 = valueStack.pop();
                        oper = operationStack.pop();
                        result = valueStack.cal(value1, value2, oper);
                        valueStack.push(result);
                    }

                    // 直接入栈
                    operationStack.push(ch);
                }

            } else {
                // 如果是两位及以上的数字就需要判断
                concat += ch;

                if (index == expression.length() - 1) {
                    valueStack.push(Integer.parseInt(concat));
                } else {
                    if (isOperation(expression.substring(index + 1, index + 2).charAt(0))) {
                        valueStack.push(Integer.parseInt(concat));
                        concat = "";
                    }
                }

            }
            index++;
            if (index == expression.length()) {
                break;
            }
        }

        // 扫描完成之后就把栈内剩余的依次出栈计算
        while (true) {
            if (operationStack.isEmpty()) {
                break;
            }
            value1 = valueStack.pop();
            value2 = valueStack.pop();
            oper = operationStack.pop();
            result = valueStack.cal(value1, value2, oper);
            valueStack.push(result);
        }

        System.out.println(expression + "=" + valueStack.pop());

    }

    private static boolean isOperation(char ch) {
        return ch == '*' || ch == '/' || ch == '-' || ch == '+';
    }

}

class ArrayStack1 {
    private int maxSize;

    private int top = -1;

    private Integer[] stacks;

    public ArrayStack1(int maxSize) {
        this.maxSize = maxSize;
        this.stacks = new Integer[maxSize];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return stacks[top];
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满了");
            return;
        }
        stacks[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("栈是空的");
            return -1;
        }

        return stacks[top--];
    }

    public int priority(int ch) {
        if (ch == '*' || ch == '/') {
            return 2;
        } else if (ch == '-' || ch == '+') {
            return 1;
        } else {
            return -1;
        }
    }

    public int cal(int value1, int value2, int ch) {
        int result;
        switch (ch) {
            case '*':
                result = value2 * value1;
                break;
            case '/':
                result = value2 / value1;
                break;
            case '+':
                result = value2 + value1;
                break;
            case '-':
                result = value2 - value1;
                break;
            default:
                result = 0;
        }

        return result;
    }
}